package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020-11-25 11:22
 *
 * https://leetcode-cn.com/problems/maximum-gap/
 */
public class _164_最大间距 {

    public int maximumGap(int[] nums) {

        if (nums == null || nums.length <= 1) {

            return 0;
        }

        int min = nums[0], max = nums[0];

        for (int num : nums) {

            if (num < min) {

                min = num;
            }

            if (num > max) {

                max = num;
            }
        }

        if (max - min == 0) {

            return 0;
        }

        int len = max - min + 1;


        // 2 999999 9999999 - 2
        int[] ints = new int[len];

        for (int num : nums) {

            ints[num - min]++;
        }

        int maxGrap = 0;

        int i = 0;

        while (i < ints.length) {

            if (ints[i] > 0) {

                int j = i + 1;

                while (j < ints.length && ints[j] == 0) {

                    j++;
                }

                if (j == ints.length) {

                    break;
                }

                if (maxGrap < j - i) {

                    maxGrap = j - i;
                }

                i = j;
            }else {

                i++;
            }
        }

        return maxGrap;
    }

}
